// https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

// 题干：给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。
//      由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
//      请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
//      要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，
//      那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

// 示例：输入：croakOfFrogs = "croakcroak"
//       输出：1

// 碎语：模拟题，但是本题的模拟策略不是特别好想
//       创建一个哈希表，记录croak五个字母出现的次数来解决这个问题

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    // r, o, a, k找一下前驱字符，是否在哈希表中存在
    // 存在，前驱个数--，当前字符++
    // 不存在，则返回-1

    // 当遍历到c时，找最后一个字符是否在哈希表中存在
    // 存在，最后一个字符--，当前字符++
    // 不存在，当前字符++
    int minNumberOfFrogs(string croakOfFrogs)
    {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n); // 对应字符，用数组来模拟哈希表

        unordered_map<char, int> index; // [x, x字符对应的下标]
        for (int i = 0 ; i < n ; i++){
            index[t[i]] = i;
        }

        for (const auto& ch : croakOfFrogs){
            if (ch == 'c'){
                if(hash[n - 1]) hash[n - 1]--;
                hash[0]++;
            }
            else {
                int i = index[ch];
                if (!hash[i - 1]) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }

        for (int i = 0 ; i < n - 1 ; i++){
            if (hash[i]) return -1;
        }

        return hash[n - 1];
    }
};

int main()
{
    Solution sol;
    string croakOfFrogs = "croakcroak";
    
    cout << sol.minNumberOfFrogs(croakOfFrogs) << endl;

    return 0;
}











